Sort transformed array

Time: O(N); Space: O(1); medium

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form

f(x) = ax^2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

Example 1:

Input: nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5

Output: [3, 9, 15, 33]

Example 2:

Input: nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5

Output: [-23, -5, 1, 7]

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def sortTransformedArray(self, nums, a, b, c):
        """
        :type nums: List[int]
        :type a: int
        :type b: int
        :type c: int
        :rtype: List[int]
        """
        func = lambda x, a, b, c : a * x * x + b * x + c

        result = []
        if not nums:
            return result

        left, right = 0, len(nums) - 1
        d = -1 if a > 0 else 1

        while left <= right:
            if d * func(nums[left], a, b, c) < d * func(nums[right], a, b, c):
                result.append(func(nums[left], a, b, c))
                left += 1
            else:
                result.append(func(nums[right], a, b, c))
                right -= 1

        return result[::d]

s = Solution1()

nums = [-4, -2, 2, 4]
a = 1
b = 3
c = 5
assert s.sortTransformedArray(nums, a, b, c) == [3, 9, 15, 33]

nums = [-4, -2, 2, 4]
a = -1
b = 3
c = 5
assert s.sortTransformedArray(nums, a, b, c) == [-23, -5, 1, 7]

See also:

https://leetcode.com/problems/sort-transformed-array

https://www.lintcode.com/problem/sort-transformed-array/description